package com.xsherl.leetcode.solution;

public class DivideTwoIntegers {

    /**
     * 运用2进制来进行模拟除法，比如：
     *  10 = 0b1010
     *   3 = 0b11
     * 所以除法过程为：
     *            1 1
     *      |---------
     *   11 | 1 0 1 0
     *          1 1
     *          ------
     *          1 0 0
     *            1 1
     *          ------
     *              1
     * 所以 10 / 3 = 0b1010 / 0b11 = 0b11 = 3
     * @param dividend
     * 被除数和除数均为 32 位有符号整数。
     * @param divisor
     * 除数不为0。
     * @return
     * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31− 1]。本题中，如果除法结果溢出，则返回 2^31− 1。
     */
    public int divide(int dividend, int divisor) {
        long x = dividend, y = divisor;
        // 计算结果符号
        boolean flag = x < 0 == y < 0;
        // 将除数和被除数转为正数，避免补码影响计算结果
        x = Math.abs(x);
        y = Math.abs(y);
        // 除数左移到和被除数位数一致
        int len = 0;
        while (y < x){
            y <<= 1;
            len++;
        }
        // 用long来存储结果，避免溢出
        long res = 0;
        for (int i = len; i >= 0 && x != 0; i--){
            // 如果被除数大于当前移动后的除数，则该位为1，被除数减去当前除数
            if (x >= y){
                x -= y;
                res |= 1L << i;
            }
            // 除数后移一位
            y >>= 1;
        }
        long l = flag ? res : -res;
        if (l > Integer.MAX_VALUE){
            l = Integer.MAX_VALUE;
        }
        return (int)l;
    }

}
